package code;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 创建了2个stack
 * 1个正常存放，另一个先把整数最大值存放进去
 * 重点在pop()，minStack一直把最小的放在最上面，虽然会重复，但是最小的一直在最上面
 * 这个很巧妙，比如我插入[3，0，-1，0，-2]
 * xStack就是[3，0，-1，0，-2]
 * minStack就是[3,0,-1,-1,-2]
 * pop第一次结果就是[3，0，-1，0]，[3,0,-1,-1]。min就是-1，再pop一次，min还是-1
 * 太神奇了
 * 当然也可以这样：
 * if(minStack.isEmpty() || minStack.peek() > x){
 *             minStack.push(x);
 *         }else{// 如果数据栈中当前最小值 < x, 则继续将最小值设置为上次的最小值
 *             minStack.push(minStack.peek());
 *         }
 *
 */


public class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;
    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

    public int top() {
       return xStack.peek();
    }

    public int min() {
        return minStack.peek();
    }
}
